﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure
{
    public delegate void HandleNode<T>(BinaryTreeNode<T> node);
    public class BinaryTree
    {

        public static BinaryTreeNode<int> GenerateBinaryTreeWithMininalHeight(int[] sorted, int start, int end)
        {
            if (end < start) return null;
            int min = (start + end) / 2;
            BinaryTreeNode<int> root = new BinaryTreeNode<int>();
            root.data = sorted[min];
            root.Left = GenerateBinaryTreeWithMininalHeight(sorted, start, min - 1);
            root.Right = GenerateBinaryTreeWithMininalHeight(sorted, min + 1, end);
            return root;
        }

        public static BinaryTreeNode<int> GenerateBinary(int[] sorted)
        {
            int start = 0;
            int end = sorted.Length - 1;
            int min = (start + end) / 2;
            BinaryTreeNode<int> root = new BinaryTreeNode<int>();
            root.data = sorted[min];
            root.Left = GenerateBinaryTreeWithMininalHeight(sorted, start, min - 1);
            Stack<int> mids = new Stack<int>();

            while(mids.Count > 0)
            {
                int mid = (start + end) / 2;
                mids.Push(mid);
                if (start < mid)
                {
                    mids.Push((start + mid - 1) / 2);
                }
                
                if (mid < end)
                {
                    mids.Push(( mid +1 + end) / 2);
                }

                
                    
            }

            root.Right = GenerateBinaryTreeWithMininalHeight(sorted, min + 1, end);
            return root;
        }



        public static BinaryTreeNode<int> GenerateBinaryTreeWithMininalHeight(int[] sorted)
        {
            BinaryTreeNode<int> root = new BinaryTreeNode<int>();
            int start = 0;
            int end = sorted.Length - 1;
            int min = (start) / 2;
            root.data = sorted[min];
            BinaryTreeNode<int> left = root.Left;
            BinaryTreeNode<int> right = root.Right;

            Stack<int> mids = new Stack<int>();
            mids.Push(end);
            int currentend;
            while (mids.Count > 0)
            {
                currentend = mids.Peek();
                while (start < currentend)
                {
                    int temp = (start + currentend) / 2;
                    mids.Push(temp);
                    currentend = temp;
                }

                mids.Pop();
                if (mids.Count > 0)
                {
                    int temp = mids.Pop();
                    start = temp;
                    Console.WriteLine(temp);
                    if (temp + 1 < mids.Peek())
                        mids.Push(temp + 1);
                }
            }
            return root;
        }


        public static bool InOrderTraverseInStack2<T>(BinaryTreeNode<T> root, HandleNode<T> handler)
        {
            bool result = true;
            Stack<BinaryTreeNode<T>> tracking = new Stack<BinaryTreeNode<T>>();
            tracking.Push(root);
            while (tracking.Count != 0)
            {
                BinaryTreeNode<T> current = null;
                while ((current = tracking.Peek()) != null)
                {
                    tracking.Push(current.Left);
                }
                tracking.Pop(); // pop null node
                if (tracking.Count != 0)
                {
                    current = tracking.Pop();
                    handler(current);
                    tracking.Push(current.Right);
                }
            }

            return result;
        }
        public static bool InOrderTraverseInStack<T>(BinaryTreeNode<T> root, HandleNode<T> handler)
        {
            bool result = true;
            Stack<BinaryTreeNode<T>> tracking = new Stack<BinaryTreeNode<T>>();
            BinaryTreeNode<T> current = root;
            while (current != null || tracking.Count != 0)
            {
                if (current != null)
                {
                    tracking.Push(current);
                    current = current.Left;
                }
                else
                {
                    current = tracking.Pop();
                    if (handler != null)
                    {
                        handler(current);
                    }
                    current = current.Right;
                }
            }
            return result;
        }

        public static bool InOrderTraverse<T>(BinaryTreeNode<T> root, HandleNode<T> handler)
        {
            if (root == null) return false;

            if (root.Left != null)
                InOrderTraverse(root.Left, handler);

            handler(root);

            if (root.Right != null)
                InOrderTraverse(root.Right, handler);

            return true;
        }

        public static bool PreOrderTraverse<T>(BinaryTreeNode<T> root, HandleNode<T> handler)
        {
            bool result = true;
            if (root != null)
            {
                if (handler != null)
                {
                    handler(root);
                }
                if (PreOrderTraverse(root.Left, handler))
                {
                    return PreOrderTraverse(root.Right, handler);
                }
            }
            return result;
        }

        public static bool PostOrderTraverse<T>(BinaryTreeNode<T> root, HandleNode<T> handler)
        {
            bool result = true;
            if (root != null)
            {

                if (PostOrderTraverse(root.Left, handler))
                {
                    if (PostOrderTraverse(root.Right, handler))
                    {
                        if (handler != null)
                        {
                            handler(root);
                        }
                    }
                }
            }
            return result;
        }

        public static void LevelTraverse(BinaryTree tree)
        {
        }


        public static bool IsBalanced(BinaryTreeNode<int> root)
        {
            return (MaxDepth(root) - MinDepth(root)) <= 1;
        }

        public static int MaxDepth(BinaryTreeNode<int> root)
        {
            if (root == null) return 0;
            return 1 + Math.Max(MaxDepth(root.Left), MaxDepth(root.Right));
        }

        public static int MinDepth(BinaryTreeNode<int> root)
        {
            if (root == null) return 0;
            return 1 + Math.Min(MinDepth(root.Left), MinDepth(root.Right));
        }
    }

    public class BinaryTreeNode<T>
    {
        public T data;
        public BinaryTreeNode<T> Left;
        public BinaryTreeNode<T> Right;
    }
}
